For each element A[i] of array A, find the closest j such that A[j] > A[i]

Posted by SamH on Stack Overflow See other posts from Stack Overflow or by SamH
Published on 2010-03-31T20:03:10Z Indexed on 2010/05/27 6:31 UTC
Read the original article Hit count: 167

Hi everyone.


Given : An array A[1..n] of real numbers.

Goal : An array D[1..n] such that

D[i] = min{ distance(i,j) : A[j] > A[i] }

or some default value (like 0) when there is no higher-valued element. I would really like to use Euclidean distance here.

Example :

A = [-1.35, 3.03, 0.73, -0.06, 0.71, -0.21, -0.12, 1.49, 1.41, 1.42]
D = [1, 0, 1, 1, 2, 1, 1, 6, 1, 2]

Is there any way to beat the obvious O(n^2) solution? The only progress I've made so far is that D[i] = 1 whenever A[i] is not a local maxima. I've been thinking a lot and have come up with NOTHING. I hope to eventually extend this to 2D (so A and D are matrices).

© Stack Overflow or respective owner

Related posts about distance

Related posts about euclidean-distance